def item(dataset):
    c1 = []
    for x in dataset:
        for y in x:
            if [y] not in c1:
                c1.append( [y] )
    c1.sort()
    return c1

def get_frequent_item(dataset, c, min_support):
    cut_branch = {}
    for x in c:
        for y in dataset:
            if set(x).issubset(set(y)):
                cut_branch[tuple(x)] = cut_branch.get(tuple(x), 0) + 1
    Fk = []
    sup_dataK = {}

    for i in cut_branch:
        if cut_branch[i] >= min_support:
            Fk.append( list(i))
            sup_dataK[i] = cut_branch[i]
    return Fk, sup_dataK

def get_candidate(Fk, K):
    ck = []

    for i in range(len(Fk)):
        for j in range(i+1, len(Fk)):
            L1 = list(Fk[i])[:K-2]
            L2 = list(Fk[j])[:K-2]
            L1.sort()
            L2.sort()

            if L1 == L2:
                if K > 2:
                    new = list(set(Fk[i]) ^ set(Fk[j]) )

                else:
                    new = set()
                for x in Fk:
                    if set(new).issubset(set(x)) and list(set(Fk[i]) | set(Fk[j])) not in ck:
                        ck.append( list(set(Fk[i]) | set(Fk[j])) )
    return ck

def Apriori(dataset, min_support = 2):
    c1 = item (dataset)
    f1, sup_1 = get_frequent_item(dataset, c1, min_support)

    F = [f1]
    sup_data = sup_1

    K = 2

    while (len(F[K-2]) > 1):
        ck = get_candidate(F[K-2], K)
        fk, sup_k = get_frequent_item(dataset, ck, min_support)

        F.append(fk)
        sup_data.update(sup_k)
        K+=1
    return F, sup_data

if __name__ == '__main__':
    dataset = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    F, sup_data = Apriori(dataset, min_support = 2)

    print("具有关联的商品是{}".format(F))
    print('------------------')
    print("对应的支持度为{}".format(sup_data))
